#ifndef LAB2_PRIMES 
#define LAB2_PRIMES 
#include <vector>

typedef size_t numbers;

template<typename T>
std::vector<T> sieve(const T max)
{
    bool* prime=new bool[(unsigned int)max+1];
        
    // 0 and 1 are not prime
    prime[0]=prime[1]=false;
    // all the rest consider prime
    for(T i=2; i<=max; ++i) prime[i]=true;


    for(T i=2; i<=ceil(sqrtl((double)max)); ++i)  
    {
        if(prime[i])
        {
            for(T j=i; j<= max/i; ++j) prime[i*j]=false;
        }
    }

    std::vector<T> small_prime;

    /*
    T small_count(0);

    for(T i=2; i<=max; ++i) 
        if(prime[i]) ++small_count;
	
	small_prime.reserve(small_count);
    */

    for(T i=0; i<=max; ++i) 
    {
        if(prime[i]) 
            small_prime.push_back(i);
    }

    delete[] prime;
    return small_prime;
}

template<typename T>
std::vector<T> get_primes_for_sharing_CRT(const numbers t, const numbers n, const T min_value, const T max_value)
{ 
    if (n < 2) throw "The number of players in threshold scheme must be greater than 2";
    if(t > n) throw "The threshold value in threshold scheme must be less than total number of players";

    const std::vector<T> primes = sieve(max_value);
    std::vector<T> result;

    //http://en.wikipedia.org/wiki/Secret_Sharing_using_the_Chinese_Remainder_Theorem#Asmuth-Bloom.27s_threshold_secret_sharing_scheme
    // choose m0
    for(std::vector<T>::const_iterator m0 = primes.begin(); m0 < primes.end(); ++m0)
    {
        // we should start the sequence from the number that is greater than min_value
        if(*m0 <= min_value) continue;

        // if all the prime numbers still not enough to build sequence of length n
        if( (numbers) (primes.end() - m0) <= n)  
            break;

        for(std::vector<T>::const_iterator m1 = m0 + 1; m1 < primes.end(); ++m1)
        {
            result.clear();
            result.push_back(*m0);
        
            for(numbers i = 0; i < n; ++i)
            {
                if(m1 + i < primes.end())
                    result.push_back(*(m1+i));
                else break;
                    //throw "Not enough prime numbers to build a sequence";
            }

             //m   * m   * ... * m 
             // 0     1           n
            if(result.size() == n + 1)
            {
                T l_product = result[0], r_product = 1;

                //m       * m       * ... * m 
                // (n-t+2)   (n-t+1)          n
                for(numbers i = n + 2 - t; i <= n; ++i)
                {
                    l_product*=result[i];
                }

                //m   * m   * ... * m 
                // 0     1           k
                for(numbers i = 1; i <= t; ++i)
                {
                    r_product*=result[i];
                }
                if(l_product<r_product) return result;
            }
            else break;
        }
    }


    // if we steel here, than something wrong and we can't build a sequence
    //throw "Sequence not builded";
    // so let's try to get more prime numbers---------------------------------
    //                                                                       |
    return get_primes_for_sharing_CRT(t, n, min_value, max_value * 2); //  <--
}
#endif /* LAB2_PRIMES */ 
